1. Field of the Invention
The present invention relates generally to a method and apparatus that enables the computation of a signal in a certain subspace, its projection that lies outside the subspace, and the orthogonal basis for a given matrix. More particularly, the present invention relates to the use of such a method or apparatus for real-time hardware applications since the method and apparatus may be utilized without matrix inversions or square root computations.
2. Description of the Prior Art
In spread spectrum systems, whether it is a communication system, a Global Positioning System (GPS) or a radar system, each transmitter may be assigned a unique code and in many instances each transmission from a transmitter is assigned a unique code. The code is nothing more than a sequence (often pseudorandom) of bits. Examples of codes include the Gold codes (used in GPS—see Kaplan, Elliot D., Editor, Understanding GPS: Principles and Applications, Artech House, 1996), Barker codes (used in radar—see Stimson, G. W., “An Introduction to Airborne Radar”, SciTech Publishing Inc., 1998), Walsh codes (used in communications systems like CDMAOne and CDMA2000—See IS-95 and IS2000 Standards). These codes may be used to spread the signal so that the resulting signal occupies some specified range of frequencies in the electromagnetic spectrum or the codes may be superimposed on another signal which might also be a coded signal.
Assigning a unique code to each transmitter allows the receiver to distinguish between different transmitters. An example of a spread spectrum system that uses unique codes to distinguish between transmitters is a GPS system.
If a single transmitter has to broadcast different messages to different receivers, such as a base-station in a wireless communication system broadcasting to different mobiles, one may use codes to distinguish between the messages for each mobile. In this scenario, each bit for a particular user is encoded using the code assigned to that user. By coding in this manner, the receiver, by knowing its own code, may decipher the message intended for it from the composite signal transmitted by the transmitter.
In some communication systems, a symbol is assigned to a sequence of bits that make up a message. For example, a long digital message may be grouped into sets of M bits and each one of these sets of M bits is a assigned to a symbol. For example, if M=6, then each set of 6 bits may assume one of 26=64 possibilities. One such possibility is 101101. Such a system would broadcast a unique waveform, called a symbol, to indicate to the receiver the sequence of bits. For example, the symbol α might denote the sequence 101101 and the symbol β might denote the sequence 110010. In the spread spectrum version of such a system, the symbols are codes. An example of such a communication system is the mobile to base-station link of CDMAOne or IS-95.
In some instances, such as in a coded radar system, each pulse is assigned a unique code so that the receiver is able to distinguish between the different pulses based on the codes.
Of course, all of these techniques may be combined to distinguish between transmitters, messages, pulses and symbols all in one single system. The key idea in all of these coded systems is that the receiver knows the codes of the message intended for it and by applying the codes correctly, the receiver may extract the message intended for it. However, such receivers are more complex than receivers that distinguish between messages by time and/or frequency alone. The complexity arises because the signal received by the receiver is a linear combination of all the coded signals present in the spectrum of interest at any given time. The receiver has to be able to extract the message intended for it from this linear combination of coded signals.
The following section presents the problem of interference in linear algebraic terms followed by a discussion of the current, generic (baseline) receivers.
Let H be a vector containing the spread signal from source no.1 and let θ1 be the amplitude of the signal from this source. Let si be the spread signals for the remaining sources and let φi be the corresponding amplitudes. Suppose the receiver is interested in source number 1, the signals from the other sources may be considered to be interference. Then, the received signal is:y=Hθ1+s2φ2+s3φ3+ . . . +spφp+n  (1)where n is the additive noise term, and p is the number of sources in the CDMA system. Let the length of the vector y be N, where N is the number of points in the integration window. This number N is selected as part of the design process as part of the trade-off between processing gain and complexity. A window of N points of y will be referred to as a segment.
In a wireless communication system, the columns of the matrix H represent the various coded signals and the elements of the vector θ are the powers of the coded signals. For example, in the base-station to mobile link of a CDMAOne system, the coded signals might be the various channels (pilot, paging, synchronization and traffic) and all their various multi-path copies from different base-stations. In the mobile to base-station link, the columns of the matrix H might be the coded signals from the mobiles and their various multi-path copies.
In a GPS system, the columns of the matrix H are the coded signals being broadcast by the GPS satellites at the appropriate code, phase and frequency offsets.
In an array application, the columns of the matrix are the steering vectors or equivalently the array pattern vectors. These vectors characterize the relative phase recorded by each antenna in the array as a function of the location and motion dynamics of the source as well as the arrangement of the antennas in the array. In the model presented above, each column of the matrix H signifies the steering vector to a particular source.
The equation (1) may now be written in the following matrix form:                                                                            y                =                                                      H                    ⁢                                                                                   ⁢                    θ                                    +                                      S                    ⁢                                                                                   ⁢                    ϕ                                    +                  n                                                                                                        =                                                                            [                      HS                      ]                                        ⁡                                          [                                                                                                    θ                                                                                                                                ϕ                                                                                              ]                                                        +                  n                                                                                          (          2          )                    where    H: spread signal matrix of the source that the receiver is demodulating    S=[s2 . . . sp]: spread signal matrix of all the other sources, i.e., the interference    φ=[φ2 . . . φp]: interference amplitude vector
Receivers that are currently in use correlate the measurement, y, with a replica of H to determine if H is present in the measurement. If H is detected, then the receiver knows the bit-stream transmitted by source number 1. Mathematically, this correlation operation is:correlation function=(HTH)−1HTy  (3)where T is the transpose operation.
Substituting for y from equation (2) illustrates the source of the power control requirement:                                                                                                                                              (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                      H                    T                                    ⁢                  y                                =                                ⁢                                                                            (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                                            H                      T                                        ⁡                                          (                                                                        H                          ⁢                                                                                                           ⁢                          θ                                                +                                                  S                          ⁢                                                                                                           ⁢                          ϕ                                                +                        n                                            )                                                                                                                                              =                                ⁢                                                                                                    (                                                                              H                            T                                                    ⁢                          H                                                )                                                                    -                        1                                                              ⁢                                          H                      T                                        ⁢                    H                    ⁢                                                                                   ⁢                    θ                                    +                                                                                    (                                                                              H                            T                                                    ⁢                          H                                                )                                                                    -                        1                                                              ⁢                                          H                      T                                        ⁢                    S                    ⁢                                                                                   ⁢                    ϕ                                    +                                                                                    (                                                                              H                            T                                                    ⁢                          H                                                )                                                                    -                        1                                                              ⁢                                          H                      T                                        ⁢                    n                                                                                                                          =                                ⁢                                  θ                  +                                                                                    (                                                                              H                            T                                                    ⁢                          H                                                )                                                                    -                        1                                                              ⁢                                          H                      T                                        ⁢                    S                    ⁢                                                                                   ⁢                    ϕ                                    +                                                                                    (                                                                              H                            T                                                    ⁢                          H                                                )                                                                    -                        1                                                              ⁢                                          H                      T                                        ⁢                    n                                                                                                          (        4        )            
It is the middle term, (HTH)−1HTSφ, in the above equation that results in the near-far problem. If the codes are orthogonal, then this term reduces to zero, which implies that the receiver has to detect θ in the presence of noise (which is (HTH)−1HTn) only. It is easy to see that as the amplitude of the other sources increases, then the term (HTH)−1HTSφ contributes a significant amount to the correlation function, which makes the detection of θ more difficult.
The normalized correlation function, (HTH)−1HT, defined above, is in fact the matched filter and is based on an orthogonal projection of y onto the space spanned by H. When H and S are not orthogonal to each other, there is leakage of the components of S into the orthogonal projection of y onto H. This leakage is geometrically illustrated in FIG. 1. Note in FIG. 1, that if S were orthogonal to H, then the leakage component goes to zero as is evident from equation 4, above. The present invention addresses an efficient method for mitigating this interference when H and S are not orthogonal.
Signal projection may be computed by means of performing the projection operation directly by computing Ps=S(STS)−1ST and then computing the other desired quantities. This direct matrix inversion method requires computing the inverse, which may be prohibitive in hardware. In addition, the direct matrix inversion method cannot handle a subspace matrix S that is singular.
Signal projection may also be computed using Householder, Givens and Gram-Schmidt methods (QR methods). These methods may be used to decompose a given matrix into an orthonormal basis. In these QR methods, the subspace matrix is first decomposed into its orthonormal representation and then the orthonormal representation is used to compute the projection of the signal. No matrix inverse computations are required, but square root computations are needed in the computation of the orthonormal representation.
Thus, there is a need in the art for a method and apparatus that provide for signal projection computations in signal processing applications without the need for any matrix inversions or square root computations, as well as to provide for the handling of a subspace matrix S which is singular.